// 解题思路
// 分析题目： 要求将一个基因序列变化至另一个基因序列。这里泛化一下就是如何把一个字符串变化为另一个字符串
// 

function minMutation(start: string, end: string, bank: string[]): number {
    // 如果两个字符串相等，那就不用找了，返回0。
    if (start === end) {
        return 0
    }
    // end必然属于bank,如果bank里面都没有end,那直接返回-1就行
    if (!bank.includes(end)) {
        return -1
    }
    // 生成bank的hashmap
    let bankMap: Map<String, boolean> = new Map();
    for (let b of bank) {
        bankMap.set(b, true);
    }
    // 可能的字符集
    let charList: string[] = ['A', 'C', 'G', 'T'];
    // 表示修改字符的次数，初始为0
    let level: number = 0;

    // 用于标记已经访问过的字符串，
    let visitedStringMap: Map<String, boolean> = new Map()
    visitedStringMap.set(start, true);

    // 用于存放 广度遍历生成的字符串集合
    let queue: string[] = [start];

    while (queue.length) {
        let currQueueLen: number = queue.length;
        // 每次一次都要将当前level生成的 字符串遍历完成后，再进入下一个level的遍历
        while (currQueueLen) {
            currQueueLen--;
            let curr: string = queue.shift();

            // 依次改变当前字符串每个位置的一个字符
            let currCharList: string[] = Array.from(curr);
            for (let i = 0; i < currCharList.length; i++) {
                let old: string = currCharList[i];
                for (let c of charList) {
                    if (c === old) {
                        continue;
                    }
                    currCharList[i] = c;
                    let next: string = currCharList.join('');

                    // 如果字符字符串没有被遍历过，同时也在bankmap中，则放入queue中，进入下一次循环
                    if (!visitedStringMap.get(next) && bankMap.get(next)) {
                        // 如果找到了目标字符串，则退出循环，返回level+1
                        // 因为next时当前level 字符串再变化一次字符产生的。
                        if (next === end) {
                            return (level + 1)
                        }
                        visitedStringMap.set(next, true);
                        queue.push(next)
                    }
                }
                currCharList[i] = old
            }
        }
        // 上一个level遍历完成，level +1
        level++;

    }
    // 没找到
    return -1;
};